package counter;

import java.util.*;
import common.ThreadID;

public class NwayCombiningTree {

    Node leaf[];
    Node root;
    int Nway;

    public NwayCombiningTree(int width, int _Nway) {
        Nway = _Nway;
        Node[] nodes = new Node[width - 1];
        nodes[0] = new Node();
        root = nodes[0];

        for (int i = 1; i < nodes.length; i++) {
            nodes[i] = new Node(nodes[(i - 1) / Nway]);
        }

        leaf = new Node[(width + 1) / Nway];

        for (int i = 0; i < leaf.length; i++) {
            leaf[i] = nodes[nodes.length - i - 1];
        }

    }

    public int getAndIncrement() throws Exception{
        Stack<Node> stack = new Stack<Node>();
        int ThreadId = ThreadID.get();
        System.out.println("currentThread.id = " + ThreadId + "call getAndIncrement");
        Node myLeaf = leaf[ThreadId / Nway];
        Node node = myLeaf;

        // precombining phase
        // 如果抢到了fisrt就会不断往上爬
        // 如果是root或者抢到了second就会返回false
        // 如果遇到了locked为true说明其他线程正在用这个节点
        while (node.precombine()) {
            node = node.parent;
        }
        Node stop = node;

        // combining phase
        node = myLeaf;
        int combined = 1; // add 1
        while (node != stop) {
            combined = node.combine(combined);
            stack.push(node);
            node = node.parent;
        }
        
        // operation phase
        int prior = stop.op(combined);
        
        // distribution phase
        while (!stack.empty()) {
            node = stack.pop();
            node.distribute(prior);
        }

        return prior;
    }

    public int getCounter() {
        return root.result;
    }
    
}
